package com.sicheng.蓝桥.练习题.线段树;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/25 12:18
 */
public class 纯数组线段树 {
    int N = 10005;
    private int n;
    long[] a = new long[N];
    long[] tree = new long[N << 2];
    long[] lazy = new long[N << 2];

    void build(int l, int r, int st) {
        if (l == r) {
            tree[st] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, st << 1);
        build(mid + 1, r, st << 1 | 1);
        up(st);
    }

    private void up(int st) {
        tree[st] = tree[st << 1] + tree[st << 1 | 1];
    }


    void update(long c, int l, int r) {
        update(c, l, r, 1, n, 1);
    }

    private void update(long c, int L, int R, int ll, int rr, int st) {
        if (L == ll && R == rr) {
            lazy[st] += c;
            tree[st] += c * (R - L + 1);
            return;
        }
        down(st, rr - ll + 1);
        int mid = (ll + rr >> 1);
        if (R <= mid)
            update(c, L, R, ll, mid, st << 1);
        else if (L > mid)
            update(c, L, R, mid + 1, rr, st << 1 | 1);
        else {
            update(c, L, mid, ll, mid, st << 1);
            update(c, mid + 1, R, mid + 1, rr, st << 1 | 1);
        }
        up(st);
    }

    long query(int L, int R) {
        return query(L, R, 1, n, 1);
    }

    long query(int L, int R, int ll, int rr, int st) {
        if (L == ll && R == rr) {
            return tree[st];
        }
        int mid = ll + rr >> 1;

        down(st, rr - ll + 1);
        long res = 0;
        if (R <= mid) {
            res += query(L, R, ll, mid, st << 1);
        } else if (L > mid) {
            res += query(L, R, mid + 1, rr, st << 1 | 1);
        } else {
            res += query(L, mid, ll, mid, st << 1);
            res += query(mid + 1, R, mid + 1, rr, st << 1 | 1);
        }

        return res;
    }

    private void down(int st, int m) {
        if (lazy[st] > 0) {
            lazy[st << 1] += lazy[st];
            lazy[st << 1 | 1] += lazy[st];
            tree[st << 1] += lazy[st] * (m - (m >> 1));
            tree[st << 1 | 1] += lazy[st] * (m >> 1);
            lazy[st] = 0;
        }
    }

    void build() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            a[i + 1] = scanner.nextInt();
        }
        build(1, n, 1);
    }

    public static void main(String[] args) {
        纯数组线段树 solution = new 纯数组线段树();
        solution.build();

        solution.update(2, 1, 8);
        solution.update(2, 3, 4);
        solution.update(2, 1, 3);
        System.out.println(solution.query(1, 4));
        System.out.println(solution.query(2, 5));
    }
}
